#希尔排序
import numpy as np
import math
def shellSoft(arr):
    interval = 1
    while interval < len(arr) // 3:
        interval = interval * 3 + 1
    while interval > 0:
        for i in range(interval, len(arr)):
            current_value = arr[i]
            prev_index = i - interval
            while prev_index >= 0 and arr[prev_index] > current_value:
                arr[prev_index + interval] = arr[prev_index]
                prev_index = prev_index - interval
            arr[prev_index + interval] = current_value
        interval = math.floor(interval / 3)
    return arr
arr = [5, 4, 3, 6, 9, 8, 2, 4]
print(shellSoft(arr))